<!DOCTYPE html>
<html lang=zh>
<head>
    <!-- hexo-inject:begin --><!-- hexo-inject:end --><!-- so meta -->
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="HandheldFriendly" content="True">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=5" />
    <meta name="description" content="作为三大经典排序算法的堆排序，借助了堆这种精巧的数据结构，实现了排序. 理解了堆结构，再理解堆排序就不难了.">
<meta property="og:type" content="article">
<meta property="og:title" content="堆与堆排序">
<meta property="og:url" content="https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/index.html">
<meta property="og:site_name" content="拿铁轮的自留地">
<meta property="og:description" content="作为三大经典排序算法的堆排序，借助了堆这种精巧的数据结构，实现了排序. 理解了堆结构，再理解堆排序就不难了.">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2019-02-27T06:26:04.000Z">
<meta property="article:modified_time" content="2021-05-31T23:57:54.880Z">
<meta property="article:author" content="拿铁轮">
<meta property="article:tag" content="algos, data-structure">
<meta name="twitter:card" content="summary">
    
    
      
        
          <link rel="shortcut icon" href="/images/favicon.ico">
        
      
      
        
          <link rel="icon" type="image/png" href="/images/favicon-192x192.png" sizes="192x192">
        
      
      
        
          <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png">
        
      
    
    <!-- title -->
    <title>堆与堆排序</title>
    <!-- styles -->
    
<link rel="stylesheet" href="/css/style.css">

    <!-- persian styles -->
    
    <!-- rss -->
    
    
      <link rel="alternate" href="/true" title="拿铁轮的自留地" type="application/atom+xml" />
    
	<!-- mathjax -->
	
<meta name="generator" content="Hexo 4.2.1"><!-- hexo-inject:begin --><!-- hexo-inject:end --></head>

<body class="max-width mx-auto px3 ltr">
    
      <!-- hexo-inject:begin --><!-- hexo-inject:end --><div id="header-post">
  <a id="menu-icon" href="#" aria-label="目录"><i class="fas fa-bars fa-lg"></i></a>
  <a id="menu-icon-tablet" href="#" aria-label="目录"><i class="fas fa-bars fa-lg"></i></a>
  <a id="top-icon-tablet" href="#" aria-label="顶部" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');" style="display:none;"><i class="fas fa-chevron-up fa-lg"></i></a>
  <span id="menu">
    <span id="nav">
      <ul>
        <!--
       --><li><a href="/">首页</a></li><!--
     --><!--
       --><li><a href="/about/">关于</a></li><!--
     --><!--
       --><li><a href="/archives/">归档</a></li><!--
     --><!--
       --><li><a href="/categories/">分类</a></li><!--
     --><!--
       --><li><a href="/tags/">标签</a></li><!--
     --><!--
       --><li><a href="/search/">搜索</a></li><!--
     -->
      </ul>
    </span>
    <br/>
    <span id="actions">
      <ul>
        
        <li><a class="icon" aria-label="上一篇" href="/2019/03/03/sword-to-offer/"><i class="fas fa-chevron-left" aria-hidden="true" onmouseover="$('#i-prev').toggle();" onmouseout="$('#i-prev').toggle();"></i></a></li>
        
        
        <li><a class="icon" aria-label="下一篇" href="/2018/03/04/zzh-ML/"><i class="fas fa-chevron-right" aria-hidden="true" onmouseover="$('#i-next').toggle();" onmouseout="$('#i-next').toggle();"></i></a></li>
        
        <li><a class="icon" aria-label="返回顶部" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fas fa-chevron-up" aria-hidden="true" onmouseover="$('#i-top').toggle();" onmouseout="$('#i-top').toggle();"></i></a></li>
        <li><a class="icon" aria-label="分享文章" href="#"><i class="fas fa-share-alt" aria-hidden="true" onmouseover="$('#i-share').toggle();" onmouseout="$('#i-share').toggle();" onclick="$('#share').toggle();return false;"></i></a></li>
      </ul>
      <span id="i-prev" class="info" style="display:none;">上一篇</span>
      <span id="i-next" class="info" style="display:none;">下一篇</span>
      <span id="i-top" class="info" style="display:none;">返回顶部</span>
      <span id="i-share" class="info" style="display:none;">分享文章</span>
    </span>
    <br/>
    <div id="share" style="display: none">
      <ul>
  <li><a class="icon" href="http://www.facebook.com/sharer.php?u=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/" target="_blank" rel="noopener"><i class="fab fa-facebook " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://twitter.com/share?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&text=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-twitter " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.linkedin.com/shareArticle?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&title=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-linkedin " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://service.weibo.com/share/share.php?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&title=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-weibo " aria-hidden="true"></i></a></li>
  <!-- <li><a class="icon" href="https://pinterest.com/pin/create/bookmarklet/?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&is_video=false&description=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-pinterest " aria-hidden="true"></i></a></li> -->
  <li><a class="icon" href="mailto:?subject=堆与堆排序&body=Check out this article: https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/"><i class="fas fa-envelope " aria-hidden="true"></i></a></li>
  <!-- <li><a class="icon" href="https://getpocket.com/save?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&title=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-get-pocket " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://reddit.com/submit?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&title=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-reddit " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.stumbleupon.com/submit?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&title=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-stumbleupon " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://digg.com/submit?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&title=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-digg " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.tumblr.com/share/link?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&name=堆与堆排序&description=&lt;p&gt;作为三大经典排序算法的堆排序，借助了堆这种精巧的数据结构，实现了排序. 理解了堆结构，再理解堆排序就不难了. &lt;/p&gt;" target="_blank" rel="noopener"><i class="fab fa-tumblr " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://news.ycombinator.com/submitlink?u=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&t=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-hacker-news " aria-hidden="true"></i></a></li> -->
</ul>



    </div>
    <div id="toc">
      <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#什么是堆"><span class="toc-number">1.</span> <span class="toc-text">什么是堆</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#堆与数组的转化"><span class="toc-number">2.</span> <span class="toc-text">堆与数组的转化</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#建堆与维护堆"><span class="toc-number">3.</span> <span class="toc-text">建堆与维护堆</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#建堆"><span class="toc-number">3.1.</span> <span class="toc-text">建堆</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#最开始的思路"><span class="toc-number">3.1.1.</span> <span class="toc-text">最开始的思路</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Floyd算法"><span class="toc-number">3.1.2.</span> <span class="toc-text">Floyd算法</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#维护堆"><span class="toc-number">3.2.</span> <span class="toc-text">维护堆</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#堆排序"><span class="toc-number">4.</span> <span class="toc-text">堆排序</span></a></li></ol>
    </div>
  </span>
</div>

    
    <div class="content index py4">
        
        <article class="post" itemscope itemtype="http://schema.org/BlogPosting">
  <header>
    
    <h1 class="posttitle" itemprop="name headline">
        堆与堆排序
    </h1>



    <div class="meta">
      <span class="author" itemprop="author" itemscope itemtype="http://schema.org/Person">
        <span itemprop="name">拿铁轮</span>
      </span>
      
    <div class="postdate">
      
        <time datetime="2019-02-27T06:26:04.000Z" itemprop="datePublished">2019-02-27</time>
        
      
    </div>


      

      
    <div class="article-tag">
        <i class="fas fa-tag"></i>
        <a class="tag-link" href="/tags/algos-data-structure/" rel="tag">algos, data-structure</a>
    </div>


    </div>
  </header>
  

  <div class="content" itemprop="articleBody">
    <p>作为三大经典排序算法的堆排序，借助了堆这种精巧的数据结构，实现了排序. 理解了堆结构，再理解堆排序就不难了. </p>
<a id="more"></a>
<p>堆排序中三点要重点掌握：</p>
<ul>
<li>怎样通过下标找到节点的父节点及子节点</li>
<li>建堆算法</li>
<li>堆调整算法</li>
</ul>
<h1 id="什么是堆"><a href="#什么是堆" class="headerlink" title="什么是堆"></a>什么是堆</h1><p>堆是一种数据结构，能够支持高效的操作.堆得一种经典实现是使用完全二叉树，这种实现也被称为完全二叉堆.事实上，堆的树结构只是它的一种逻辑结构，也就是画在纸的，在我们脑海中想象出来的，实际内存中的物理结构，常常是使用数组. 有时候堆也被称为<em>优先级队列</em>，这是它的逻辑上的名字，别人用起来就好像是这种结构具有某种优先级.一般来说，堆分两种: 大根堆和小根堆.作为一种数据结构，考察堆的增删改查操作.修改在堆中并不常见，忽略. 查找操作也只限定在查找最大值/最小值上. 增加操作通常加在堆的最后，删除操作通常删除根节点.</p>
<h1 id="堆与数组的转化"><a href="#堆与数组的转化" class="headerlink" title="堆与数组的转化"></a>堆与数组的转化</h1><p>堆结构和数组具有很好的对应，即给定一个规模为n的二叉堆，给堆得层序遍历序列对应的就是一个数组，大小同样为n. 从而，有了一个数组，就能把这个数组当成堆来用.使用三个公式即可找到任意节点i的父节点，左节点和右节点（如果有的话）. 假设大小为n的数组arr，下标记为$i = 0, 1, \cdots, n - 1$, 则其左节点的下标为 $2 \cdot i + 1$, 其右节点（如果有）的下标为 $2 \cdot i + 2$, 对于下标为j的节点，其父节点的下标为 $(j - 1) / 2$, 注意当$j = 0$ 时 其父节点时自身，$(0 - 1) / 2 = 0$ 不会越界.</p>
<h1 id="建堆与维护堆"><a href="#建堆与维护堆" class="headerlink" title="建堆与维护堆"></a>建堆与维护堆</h1><p>堆中，最重要的两种操作是：建堆和维护堆.建堆是指给定一组数据，比如就是一个数组，通过某种算法将其调整为一个堆（调整操作也就是调整数组中元素的位置）；维护堆是指当增删后的堆不再是一个堆时，用某种算法将其再次调整为一个合法的堆.一个合法的堆是指该堆满足<strong>堆序性</strong>，对于大根堆，堆序性是指根节点是堆中最大值，对于小根堆，定义类似.</p>
<p>已知对于一棵高度为h的满二叉树，其规模$n = 2^{(h + 1)}- 1$, 即 $h = O(\log n)$，</p>
<p>下面讨论建堆算法和堆调整算法.</p>
<h2 id="建堆"><a href="#建堆" class="headerlink" title="建堆"></a>建堆</h2><h3 id="最开始的思路"><a href="#最开始的思路" class="headerlink" title="最开始的思路"></a>最开始的思路</h3><p>任意给定一个大小为n的数组，从零位置的元素出发，即从空堆出发，不断将新元素加入堆中，堆的增加操作复杂度为O(logn), 从而要建立一个大小为n的堆，复杂度为：</p>
<script type="math/tex; mode=display">\log 1 + \log 2 + ... + \log n = O(n\log n)</script><p>更细致的复杂度分析，假定一个规模为n的堆高度是h, 则该堆中第i层的节点个数是2^i, 其中 0 &lt;= i &lt; h, 建堆需要每一个元素i都上溯，则复杂度：</p>
<script type="math/tex; mode=display">1 \cdot 2^1 + 2 \cdot 2^2 + ... + h \cdot 2^h = O(n \log n)</script><h3 id="Floyd算法"><a href="#Floyd算法" class="headerlink" title="Floyd算法"></a>Floyd算法</h3><p>算法一过于复杂，建堆就需要O(nlogn)，还不如使用快排或归排.我们需要一个更高效的算法. 从相反的思路考虑，假设堆已经建好了，我们需要做的是调整堆，即下沉操作.时间复杂度： </p>
<script type="math/tex; mode=display">(h - 1) \cdot 2^1 + (h - 2) \cdot 2^2 + ... + (h - h) \cdot 2^h = O(n)</script><p>Done!</p>
<h2 id="维护堆"><a href="#维护堆" class="headerlink" title="维护堆"></a>维护堆</h2><p>堆的维护发生在增加或删除操作之后.</p>
<p>对于增加操作，新元素被添加至树的最后一层，最坏情况下该元素需要O(logn)次操作上溯至根节点的位置，才能保证对的合法性；对于删除操作，根节点被删除，堆的最后一个节点被移至根节点的位置，最多需要O(logn)次操作下沉至最后一层，才能保证新堆的合法性.</p>
<p>综上，堆的调整算法复杂度是O(logn).</p>
<h1 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h1><p>有了堆结构，排序就变得很简单了.只需O(1)的辅助空间，O(nlogn)的时间就能实排序.给定一个无序数组，该数组被看作是  [堆(无序区) | 有序区]， 堆排序的过程就是不断交换无序区中的首尾元素（等效于弹出最大值，然后用末元素顶替根元素）， 由此堆不再合法，调用调整算法使其重新称为一个合法堆， 此番操作后有序区扩大，无序区收缩，反复这个过程，遇到空堆时算法终止·</p>
<p>复杂度分析: 堆中n个元素都历经交换和堆调整算法，耗时O(logn)，从而最终复杂度为 O(nlogn).</p>

  </div>
</article>

    <div class="blog-post-comments">
        <div id="disqus_thread">
            <noscript>加载评论需要在浏览器启用 JavaScript 脚本支持。</noscript>
        </div>
    </div>



        
          <div id="footer-post-container">
  <div id="footer-post">

    <div id="nav-footer" style="display: none">
      <ul>
         
          <li><a href="/">首页</a></li>
         
          <li><a href="/about/">关于</a></li>
         
          <li><a href="/archives/">归档</a></li>
         
          <li><a href="/categories/">分类</a></li>
         
          <li><a href="/tags/">标签</a></li>
         
          <li><a href="/search/">搜索</a></li>
        
      </ul>
    </div>

    <div id="toc-footer" style="display: none">
      <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#什么是堆"><span class="toc-number">1.</span> <span class="toc-text">什么是堆</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#堆与数组的转化"><span class="toc-number">2.</span> <span class="toc-text">堆与数组的转化</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#建堆与维护堆"><span class="toc-number">3.</span> <span class="toc-text">建堆与维护堆</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#建堆"><span class="toc-number">3.1.</span> <span class="toc-text">建堆</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#最开始的思路"><span class="toc-number">3.1.1.</span> <span class="toc-text">最开始的思路</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Floyd算法"><span class="toc-number">3.1.2.</span> <span class="toc-text">Floyd算法</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#维护堆"><span class="toc-number">3.2.</span> <span class="toc-text">维护堆</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#堆排序"><span class="toc-number">4.</span> <span class="toc-text">堆排序</span></a></li></ol>
    </div>

    <div id="share-footer" style="display: none">
      <ul>
  <li><a class="icon" href="http://www.facebook.com/sharer.php?u=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/" target="_blank" rel="noopener"><i class="fab fa-facebook fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://twitter.com/share?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&text=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-twitter fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.linkedin.com/shareArticle?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&title=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-linkedin fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://service.weibo.com/share/share.php?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&title=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-weibo fa-lg" aria-hidden="true"></i></a></li>
  <!-- <li><a class="icon" href="https://pinterest.com/pin/create/bookmarklet/?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&is_video=false&description=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-pinterest fa-lg" aria-hidden="true"></i></a></li> -->
  <li><a class="icon" href="mailto:?subject=堆与堆排序&body=Check out this article: https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/"><i class="fas fa-envelope fa-lg" aria-hidden="true"></i></a></li>
  <!-- <li><a class="icon" href="https://getpocket.com/save?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&title=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-get-pocket fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://reddit.com/submit?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&title=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-reddit fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.stumbleupon.com/submit?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&title=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-stumbleupon fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://digg.com/submit?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&title=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-digg fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="http://www.tumblr.com/share/link?url=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&name=堆与堆排序&description=&lt;p&gt;作为三大经典排序算法的堆排序，借助了堆这种精巧的数据结构，实现了排序. 理解了堆结构，再理解堆排序就不难了. &lt;/p&gt;" target="_blank" rel="noopener"><i class="fab fa-tumblr fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="https://news.ycombinator.com/submitlink?u=https://hillbamboo.gitee.io/2019/02/27/heap-heapsort/&t=堆与堆排序" target="_blank" rel="noopener"><i class="fab fa-hacker-news fa-lg" aria-hidden="true"></i></a></li> -->
</ul>



    </div>

    <div id="actions-footer">
        <a id="menu" class="icon" href="#" onclick="$('#nav-footer').toggle();return false;"><i class="fas fa-bars fa-lg" aria-hidden="true"></i> 菜单</a>
        <a id="toc" class="icon" href="#" onclick="$('#toc-footer').toggle();return false;"><i class="fas fa-list fa-lg" aria-hidden="true"></i> 目录</a>
        <a id="share" class="icon" href="#" onclick="$('#share-footer').toggle();return false;"><i class="fas fa-share-alt fa-lg" aria-hidden="true"></i> 分享</a>
        <a id="top" style="display:none" class="icon" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fas fa-chevron-up fa-lg" aria-hidden="true"></i> 返回顶部</a>
    </div>

  </div>
</div>

        
        <footer id="footer">
  <div class="footer-left">
    Copyright &copy;
    
    
    2017-2022
    拿铁轮
  </div>
  <div class="footer-right">
    <nav>
      <ul>
        <!--
       --><li><a href="/">首页</a></li><!--
     --><!--
       --><li><a href="/about/">关于</a></li><!--
     --><!--
       --><li><a href="/archives/">归档</a></li><!--
     --><!--
       --><li><a href="/categories/">分类</a></li><!--
     --><!--
       --><li><a href="/tags/">标签</a></li><!--
     --><!--
       --><li><a href="/search/">搜索</a></li><!--
     -->
      </ul>
    </nav>
  </div>
</footer>

    </div>
    <!-- styles -->



  <link rel="preload" as="style" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.15.2/css/all.min.css" crossorigin="anonymous" onload="this.onload=null;this.rel='stylesheet'"/>


    <!-- jquery -->
 
  <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.6.0/jquery.min.js" crossorigin="anonymous"></script> 




<!-- clipboard -->

  
    <script src="https://cdnjs.cloudflare.com/ajax/libs/clipboard.js/2.0.7/clipboard.min.js" crossorigin="anonymous"></script> 
  
  <script type="text/javascript">
  $(function() {
    // copy-btn HTML
    var btn = "<span class=\"btn-copy tooltipped tooltipped-sw\" aria-label=\"复制到粘贴板！\">";
    btn += '<i class="far fa-clone"></i>';
    btn += '</span>'; 
    // mount it!
    $(".highlight table").before(btn);
    var clip = new ClipboardJS('.btn-copy', {
      text: function(trigger) {
        return Array.from(trigger.nextElementSibling.querySelectorAll('.code')).reduce((str,it)=>str+it.innerText+'\n','')
      }
    });
    clip.on('success', function(e) {
      e.trigger.setAttribute('aria-label', "复制成功！");
      e.clearSelection();
    })
  })
  </script>


<script src="/js/main.js"></script>

<!-- search -->

<!-- Google Analytics -->

<!-- Baidu Analytics -->

<!-- Cloudflare Analytics -->

<!-- Umami Analytics -->

<!-- Disqus Comments -->

    <script type="text/javascript">
        var disqus_shortname = 'cactus-1';

        (function(){
            var dsq = document.createElement('script');
            dsq.type = 'text/javascript';
            dsq.async = true;
            dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
            (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
        }());
    </script>

<!-- utterances Comments --><!-- hexo-inject:begin --><!-- Begin: Injected MathJax -->
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({"tex2jax":{"inlineMath":[["$","$"],["\\(","\\)"]],"skipTags":["script","noscript","style","textarea","pre","code"],"processEscapes":true},"TeX":{"equationNumbers":{"autoNumber":"AMS"}}});
</script>

<script type="text/x-mathjax-config">
  MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
      all[i].SourceElement().parentNode.className += ' has-jax';
    }
  });
</script>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js">
</script>
<!-- End: Injected MathJax -->
<!-- hexo-inject:end -->

</body>
</html>
